/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class MaximalRectangle {

	/**
	Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
	http://discuss.leetcode.com/questions/260/maximal-rectangle
	
	http://hi.baidu.com/mzry1992/item/030f9740e0475ef7dc0f6cba
	 DP
	 Case 1 -- matrix(i, j) = 1; // nonblocker
	 H(row, col) = H(row - 1, col)
	 L(row, col) = max(L(row - 1, col), the position of left nearest  blocker on current row)
	 R(row, col) = min(R(row - 1, col), the position of right nearest blocker on current row)
	 
	 Case 2 -- matrix(i, j) = 0 // blocker
	 H(row, col) = 0
	 L(row, col) = 0
	 R(row, col) = n
	 */
	public int maximalRectangle(char[][] matrix) {
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return 0;
		}
		int max = 0;
		int rows = matrix.length;
		int cols = matrix[0].length;
		int[] height = new int[cols];
		int[] left = new int[cols];
		int[] right = new int[cols];
		for (int i = 0; i < right.length; i++) {
			right[i] = cols;
		}

		for (int row = 0; row < rows; row++) {
			int preLeft = 0;
			for (int col = 0; col < cols; col++) {
				if (matrix[row][col] == '1') { //nonblock
					height[col]++;
					left[col] = Math.max(preLeft, left[col]);
				} else {
					preLeft = col + 1;
					height[col] = 0;
					left[col] = 0;
				}
			}
			int preRight = cols;
			for (int col = cols - 1; col >= 0; col--) {
				if (matrix[row][col] == '1') {
					right[col] = Math.min(preRight, right[col]);
					max = Math.max(max, height[col] * (right[col] - left[col]));
				} else {
					preRight = col;
					right[col] = cols;
				}
			}
		}

		return max;
	}

	// http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529
	//	public int maximalRectangleB(char[][] matrix) {
	//
	//	}

	public int maximalRectangleBruteForce(char[][] matrix) {
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return 0;
		}

		int maxArea = 0;

		int rows = matrix.length;
		int cols = matrix[0].length;

		Point topRight = new Point(0, 0);
		Point buttomLeft = new Point(0, 0);

		for (topRight.row = 0; topRight.row < rows; topRight.row++) {
			for (topRight.col = 0; topRight.col < cols; topRight.col++) {
				for (buttomLeft.row = topRight.row; buttomLeft.row < rows; buttomLeft.row++) {
					for (buttomLeft.col = topRight.col; buttomLeft.col < rows; buttomLeft.col++) {
						int area = calcArea(topRight, buttomLeft);
						if (area > maxArea
								&& areAllOnes(matrix, topRight, buttomLeft))
							maxArea = area;
					}
				}
			}
		}

		return maxArea;
	}

	boolean areAllOnes(char[][] matrix, Point topRight, Point buttomLeft) {
		for (int row = topRight.row; row <= buttomLeft.row; row++) {
			for (int col = topRight.col; col < buttomLeft.col; col++) {
				if (matrix[row][col] == 0)
					return false;
			}
		}

		return true;
	}

	// #####################################
	// ########## NOT WORK BEGIN ###########
	// #####################################
	class Point {
		int row;
		int col;

		public Point(int row, int col) {
			this.row = row;
			this.col = col;
		}
	}

	int maxAllOneArea(int[][] matrix) {

		int maxArea = 0;
		if (matrix == null || matrix.length == 0) {
			return maxArea;
		}

		int rows = matrix.length;
		int cols = matrix[0].length;

		Point[] cache = new Point[cols];

		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (matrix[row][col] == 0) {
					cache[col] = null;
				} else {
					Point p = new Point(row, col);
					Point currP = p;
					int area = 1;
					if (col > 0 && cache[col - 1] != null) {
						int c = cache[col - 1] == null ? col
								: cache[col - 1].col;
						int r = row;
						p = new Point(r, c);
						area = calcArea(p, currP);
					}
					if (cache[col] != null) {
						int c = col;
						int r = cache[col] == null ? row : cache[col].row;
						Point tempP = new Point(r, c);
						int tempArea = calcArea(tempP, currP);
						if (tempArea > area) {
							area = tempArea;
							p = tempP;
						}
					}
					if (col > 0 && cache[col - 1] != null && cache[col] != null) {
						int c = Math.max(cache[col].col, cache[col - 1].col);
						int r = Math.max(cache[col].row, cache[col - 1].row);
						Point tempP = new Point(r, c);
						int tempArea = calcArea(tempP, currP);
						if (tempArea > area) {
							area = tempArea;
							p = tempP;
						}
					}
					cache[col] = p;
					maxArea = Math.max(maxArea, area);
				}
			}
		}

		return maxArea;
	}

	int calcArea(Point p1, Point p2) {
		return (Math.abs(p1.row - p2.row) + 1)
				* (Math.abs(p1.col - p2.col) + 1);
	}

	// #####################################
	// ########## NOT WORK END #############
	// #####################################
	/**
	 * 
	 */
	public MaximalRectangle() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MaximalRectangle maosr = new MaximalRectangle();
		int[][] matrix = { { 0, 0, 1, 0, 0 }, { 0, 1, 1, 0, 0 },
				{ 0, 1, 1, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0 },
				{ 0, 1, 0, 0, 0 } };
		int area = maosr.maxAllOneArea(matrix);
		System.out.printf("max are is %d", area);

	}

}
